package Algorithm;

/**
 * 求解两个数的最大公因数
 *
 * @author 23737
 * @time 2021.12.5
 */
public class CommonFactor {
    public static void main(String[] args) {
        System.out.println("暴力解法： " + new CommonFactor().getGreatestNumber(100, 80));
        System.out.println("辗转相除： " + new CommonFactor().getGreatestNumber2(100, 80));
        System.out.println("更相减损： " + new CommonFactor().getGreatestNumber3(100, 80));
    }

    //暴力解法
    public int getGreatestNumber(int a, int b) {
        int small = a > b ? b : a;
        int big = a > b ? a : b;
        if (small % big == 0) {
            return small;
        }
        for (int i = small / 2; i > 1; i--) {
            if (small % i == 0 && big % i == 0) {
                return i;
            }
        }
        return 1;
    }

    //解法优化（辗转相除法）
    public int getGreatestNumber2(int a, int b) {
        int small = a > b ? b : a;
        int big = a > b ? a : b;
        if (big % small == 0) {
            return small;
        }
        return getGreatestNumber2(big % small, small);
    }

    //解法再优化（更相减损法）
    public int getGreatestNumber3(int a, int b) {
        if (a == b) {
            return a;
        }
        int small = a > b ? b : a;
        int big = a > b ? a : b;
        return getGreatestNumber3(big - small, small);
    }

}
